{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Units on a Truck"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumUnits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #卡车上的最大单元数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请你将一些箱子装在 <strong>一辆卡车</strong> 上。给你一个二维数组 <code>boxTypes</code> ，其中 <code>boxTypes[i] = [numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub>]</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>numberOfBoxes<sub>i</sub></code> 是类型 <code>i</code> 的箱子的数量。</li>\n",
    "\t<li><code>numberOfUnitsPerBox<sub>i</sub></code><sub> </sub>是类型 <code>i</code> 每个箱子可以装载的单元数量。</li>\n",
    "</ul>\n",
    "\n",
    "<p>整数 <code>truckSize</code> 表示卡车上可以装载 <strong>箱子</strong> 的 <strong>最大数量</strong> 。只要箱子数量不超过 <code>truckSize</code> ，你就可以选择任意箱子装到卡车上。</p>\n",
    "\n",
    "<p>返回卡车可以装载 <strong>单元</strong> 的 <strong>最大</strong> 总数<em>。</em></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>箱子的情况如下：\n",
    "- 1 个第一类的箱子，里面含 3 个单元。\n",
    "- 2 个第二类的箱子，每个里面含 2 个单元。\n",
    "- 3 个第三类的箱子，每个里面含 1 个单元。\n",
    "可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。\n",
    "单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10\n",
    "<strong>输出：</strong>91\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= boxTypes.length <= 1000</code></li>\n",
    "\t<li><code>1 <= numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub> <= 1000</code></li>\n",
    "\t<li><code>1 <= truckSize <= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-units-on-a-truck](https://leetcode.cn/problems/maximum-units-on-a-truck/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-units-on-a-truck](https://leetcode.cn/problems/maximum-units-on-a-truck/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[2,2],[3,1]]\\n4', '[[5,10],[2,5],[4,7],[3,9]]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x:x[1],reverse = True)\n",
    "        count = 0\n",
    "        znum = 0\n",
    "        for i in range(len(boxTypes)):\n",
    "            if truckSize-count<=boxTypes[i][0]:\n",
    "                znum+=(truckSize-count)*boxTypes[i][1]\n",
    "                break\n",
    "            else:\n",
    "                count+=boxTypes[i][0]\n",
    "                znum+=boxTypes[i][0]*boxTypes[i][1]\n",
    "        return znum\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, bs: List[List[int]], k: int) -> int:\n",
    "        bs.sort(key=lambda x: -x[1])\n",
    "        n, ans = len(bs), 0\n",
    "        idx, cnt = 0, 0\n",
    "        while idx < n and cnt < k:\n",
    "            a, b, c = bs[idx][0], bs[idx][1], min(bs[idx][0], k - cnt)\n",
    "            cnt, ans = cnt + c, ans + b * c\n",
    "            idx += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        ans = 0\n",
    "        for a, b in sorted(boxTypes, key=lambda x: -x[1]):\n",
    "            ans += b * min(truckSize, a)\n",
    "            truckSize -= a\n",
    "            if truckSize <= 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        # 简化的背包问题，限制不是物品重量而是物品数量\n",
    "        # 贪心，优先选择单元数最多的箱子\n",
    "        boxTypes.sort(key = lambda x: x[1], reverse = True)\n",
    "        def ans(boxes, restSize):\n",
    "            if not boxes:\n",
    "                return 0\n",
    "            maxBox = boxes.pop(0)\n",
    "            maxBoxNum = maxBox[0]\n",
    "            maxBoxSize = maxBox[1]\n",
    "            if restSize > maxBoxNum:\n",
    "                return maxBoxNum*maxBoxSize + ans(boxes, restSize-maxBoxNum)\n",
    "            else:\n",
    "                return restSize*maxBoxSize\n",
    "        return ans(boxTypes, truckSize)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxes = sorted(boxTypes, key = lambda item: item[1], reverse=True)\n",
    "        res = 0\n",
    "        for box_num, box_unit in boxes:\n",
    "            if box_num >= truckSize:\n",
    "                res += truckSize *  box_unit\n",
    "                break\n",
    "            else:\n",
    "                res += box_num * box_unit\n",
    "                truckSize -= box_num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(reverse=True, key=lambda x: x[1])\n",
    "        s, n = 0, 0\n",
    "        for k, v in boxTypes:\n",
    "            s += k * v\n",
    "            n += k\n",
    "            if n == truckSize:\n",
    "                return s\n",
    "            elif n > truckSize:\n",
    "                while n > truckSize:\n",
    "                    n -= 1\n",
    "                    s -= v\n",
    "                return s\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n",
    "\n",
    "            \n",
    "            \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:-x[1])\n",
    "\n",
    "        cnt = boxTypes[0][0] \n",
    "        result = 0\n",
    "\n",
    "        while cnt <= truckSize:\n",
    "            result += boxTypes[0][0] * boxTypes[0][1]\n",
    "            boxTypes.pop(0)\n",
    "            if boxTypes == []:\n",
    "                break\n",
    "            cnt += boxTypes[0][0]\n",
    "        \n",
    "        if cnt > truckSize:\n",
    "            cnt -= boxTypes[0][0]\n",
    "            result += (truckSize - cnt) * boxTypes[0][1]\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes = sorted(boxTypes, key= lambda x: x[1], reverse = True)\n",
    "        sum_ = 0\n",
    "        print(boxTypes)\n",
    "        for i in range(len(boxTypes)):\n",
    "            if truckSize - boxTypes[i][0] >= 0:\n",
    "                truckSize -= boxTypes[i][0]\n",
    "                sum_ += boxTypes[i][0] * boxTypes[i][1]\n",
    "            else:\n",
    "                sum_ += truckSize * boxTypes[i][1]\n",
    "                break\n",
    "        return sum_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        c=0\n",
    "        for i,j in boxTypes:\n",
    "            if i>=truckSize:\n",
    "                c+=truckSize*j\n",
    "                break\n",
    "            c+=i*j\n",
    "            truckSize-=i\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(reverse=True, key=lambda x:x[1])\n",
    "        print(boxTypes[0][0])\n",
    "        count=0\n",
    "        i=0\n",
    "        while truckSize>0:\n",
    "            count+=min(truckSize,boxTypes[i][0])*boxTypes[i][1]\n",
    "            truckSize-=min(truckSize,boxTypes[i][0])\n",
    "            i+=1\n",
    "            if i>=len(boxTypes): break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        ans = 0\n",
    "        for a, b in sorted(boxTypes, key=lambda x: -x[1]):\n",
    "            ans += b * min(truckSize, a)\n",
    "            truckSize -= a\n",
    "            if truckSize <= 0:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:x[1],reverse=True)\n",
    "        res=0\n",
    "        for numberOfBoxes,numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes>=truckSize:\n",
    "                res+=truckSize*numberOfUnitsPerBox\n",
    "                break\n",
    "            res+=numberOfBoxes*numberOfUnitsPerBox\n",
    "            truckSize-=numberOfBoxes\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1],reverse=True)\n",
    "        res = 0\n",
    "        for i in boxTypes:\n",
    "            if i[0]<truckSize:\n",
    "                res += i[0]*i[1]\n",
    "            else:\n",
    "                res += truckSize*i[1]\n",
    "                return res\n",
    "            truckSize -= i[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(reverse=True, key=lambda x: x[1])\n",
    "        ans = 0\n",
    "        for k, v in boxTypes:\n",
    "            if k > truckSize:\n",
    "                ans += truckSize * v\n",
    "                break\n",
    "            ans += k * v\n",
    "            truckSize -= k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(reverse=True, key=lambda x: x[1])\n",
    "        i, s, n = 0, 0, 0\n",
    "        for k, v in boxTypes:\n",
    "            for _ in range(k):\n",
    "                if n >= truckSize:\n",
    "                    return s\n",
    "                s += v\n",
    "                n += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda boxType: boxType[1], reverse=True)\n",
    "        result = 0\n",
    "        for boxNum, unitNumPerBox in boxTypes:\n",
    "            usedNum = min(boxNum, truckSize)\n",
    "            result += usedNum * unitNumPerBox\n",
    "            truckSize -= usedNum\n",
    "            if truckSize <= 0:\n",
    "                break\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        ans=0\n",
    "        for a, b in sorted(boxTypes, key=lambda x: -x[1]):\n",
    "            ans += b * min(truckSize, a)\n",
    "            truckSize -= a\n",
    "            if truckSize <= 0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "    \n",
    "        boxTypes = sorted(boxTypes, key = lambda x: -x[-1])\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in boxTypes:\n",
    "            if cnt1 + i[0] <= truckSize:\n",
    "                cnt1 += i[0]\n",
    "                cnt2 += i[1] * i[0]             \n",
    "            else:\n",
    "                cnt2 += i[1] * (truckSize - cnt1)\n",
    "                return cnt2\n",
    "            \n",
    "        return cnt2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        lis = sorted(boxTypes, key = lambda x:x[1], reverse = True)\n",
    "        #print(lis)\n",
    "        units = 0\n",
    "        cur_size = 0\n",
    "        for num, unit in lis:\n",
    "            units += num * unit\n",
    "            cur_size += num\n",
    "            if cur_size > truckSize:\n",
    "                de = cur_size - truckSize\n",
    "                units -= de * unit\n",
    "                return units\n",
    "        return units"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        sb = sorted(boxTypes, key=lambda row:row[1], reverse=True)\n",
    "        ans, cursize = 0, 0\n",
    "        for box in sb:\n",
    "            if cursize + box[0] <= truckSize:\n",
    "                ans += box[0] * box[1]\n",
    "                cursize += box[0]\n",
    "            else:\n",
    "                ans += (truckSize - cursize) * box[1]\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        sum = 0\n",
    "        for item in boxTypes:\n",
    "            if item[0] >= truckSize:\n",
    "                sum += item[-1]*truckSize\n",
    "                break\n",
    "            else:\n",
    "                sum += item[0]*item[-1]\n",
    "                truckSize -= item[0]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x: x[1])\n",
    "        boxTypes = boxTypes[::-1]\n",
    "\n",
    "        sum_tracks = 0\n",
    "        sum_units = 0\n",
    "\n",
    "        for t, u in boxTypes:  \n",
    "            if sum_tracks + t <= truckSize:\n",
    "                sum_units += t * u \n",
    "                sum_tracks += t \n",
    "            else:\n",
    "                left_truck = truckSize - sum_tracks\n",
    "                sum_units += left_truck * u \n",
    "                break\n",
    "        \n",
    "        return sum_units\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res=0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes>=truckSize:\n",
    "                res+=truckSize*numberOfUnitsPerBox\n",
    "                break\n",
    "            res+=numberOfBoxes*numberOfUnitsPerBox\n",
    "            truckSize-=numberOfBoxes\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        leftTruckSize = truckSize\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes < leftTruckSize:\n",
    "                res += numberOfBoxes * numberOfUnitsPerBox\n",
    "                leftTruckSize -= numberOfBoxes\n",
    "            else:\n",
    "                res += leftTruckSize * numberOfUnitsPerBox\n",
    "                return res\n",
    "        return res\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/maximum-units-on-a-truck/solutions/1967382/qia-che-shang-de-zui-da-dan-yuan-shu-by-ynaqv/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x: -x[1])\n",
    "        cont = 0\n",
    "        for i in range(len(boxTypes)):\n",
    "            if truckSize >= boxTypes[i][0]:\n",
    "                cont += boxTypes[i][0] * boxTypes[i][1]\n",
    "                truckSize -= boxTypes[i][0]\n",
    "            else:\n",
    "                cont += truckSize * boxTypes[i][1]\n",
    "                break\n",
    "        return cont"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:(-x[1]))\n",
    "        ans = 0\n",
    "        for i, (cnt, size) in enumerate(boxTypes):\n",
    "            mn = min(truckSize, cnt)\n",
    "            ans += mn * size\n",
    "            truckSize -= mn\n",
    "            if truckSize == 0:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "        # m = truckSize\n",
    "        # f = [0] * (m + 1) \n",
    "        # for cnt, size in boxTypes:\n",
    "        #     for i in range(m, -1, -1):\n",
    "        #         for j in range(1, cnt + 1):\n",
    "        #             if i >= j:\n",
    "        #                 f[i] = max(f[i], f[i - j] + j * size)\n",
    "        # return f[-1] + ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1],reverse=True)\n",
    "        res = 0\n",
    "        for i in boxTypes:\n",
    "            if i[0]<truckSize:\n",
    "                res += i[0]*i[1]\n",
    "            else:\n",
    "                res += truckSize*i[1]\n",
    "                return res\n",
    "            truckSize -= i[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes = sorted(boxTypes, key=lambda x: x[1], reverse=True)\n",
    "        # print(boxTypes)\n",
    "        # 记录最大总数\n",
    "        s = 0\n",
    "        # 记录剩余可装箱子数\n",
    "        remainder = truckSize\n",
    "        # 记录遍历下标\n",
    "        idx = 0\n",
    "        while idx < len(boxTypes):\n",
    "            if remainder >= boxTypes[idx][0]:\n",
    "                s += boxTypes[idx][0] * boxTypes[idx][1]\n",
    "                remainder -= boxTypes[idx][0]\n",
    "            elif remainder > 0:\n",
    "                s += remainder * boxTypes[idx][1]\n",
    "                remainder -= remainder\n",
    "            else:\n",
    "                break\n",
    "            idx += 1\n",
    "        \n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():    \n",
    "    def maximumUnits(self, boxTypes, truckSize):\n",
    "        boxTypes = sorted(boxTypes, key = lambda x : x[1], reverse = True)\n",
    "        ret = 0\n",
    "        for box in boxTypes:\n",
    "            ret += min(truckSize, box[0]) * box[1]\n",
    "            truckSize -= min(truckSize, box[0])\n",
    "            if truckSize <= 0:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: (x[1],x[0]),reverse=True)\n",
    "        res = 0\n",
    "        for x in boxTypes:\n",
    "            if x[0] < truckSize:\n",
    "                res += x[0] * x[1]\n",
    "            else:\n",
    "                res += truckSize * x[1]\n",
    "                return res\n",
    "            truckSize -= x[0]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "      dict1 = {}\n",
    "      for i in boxTypes:\n",
    "        if i[-1] not in dict1:\n",
    "          dict1[i[-1]] = i[0]\n",
    "        else:\n",
    "          dict1[i[-1]] += i[0]\n",
    "      key = list(dict1.keys())\n",
    "      key.sort(reverse=True)\n",
    "      sum = 0\n",
    "      for i in key:\n",
    "        if truckSize:\n",
    "          if dict1[i] < truckSize:\n",
    "            sum += dict1[i] * i\n",
    "            truckSize -= dict1[i]\n",
    "          else:\n",
    "            sum += truckSize * i\n",
    "            truckSize = 0\n",
    "        else:\n",
    "          break\n",
    "      return sum\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        res = 0\n",
    "        boxTypes = sorted(boxTypes,key=lambda x:(-x[1],x[0]))\n",
    "        for box in boxTypes:\n",
    "            if box[0] <= truckSize:\n",
    "                res += box[0]*box[1]\n",
    "                truckSize -= box[0]\n",
    "            else:\n",
    "                res += truckSize*box[1]\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maximumUnits(self, boxTypes, truckSize):\n",
    "        \"\"\"\n",
    "        :type boxTypes: List[List[int]]\n",
    "        :type truckSize: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        boxTypes.sort(key=lambda x: -x[1])\n",
    "        sumSize = 0\n",
    "        num = 0\n",
    "        while num < truckSize:\n",
    "            if boxTypes == []:\n",
    "                break\n",
    "            sumSize += boxTypes[0][1]\n",
    "            boxTypes[0][0] -= 1\n",
    "            if boxTypes[0][0] == 0:\n",
    "                boxTypes.pop(0)\n",
    "            num += 1\n",
    "\n",
    "        return sumSize\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x: x[1], reverse=True)\n",
    "        s = 0\n",
    "        for i in boxTypes:\n",
    "            if truckSize > i[0]:\n",
    "                s += i[1] * i[0]\n",
    "                truckSize -= i[0]\n",
    "            else:\n",
    "                return s + i[1]*truckSize\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:-x[1])\n",
    "        sum=0\n",
    "        for i in boxTypes:\n",
    "            if truckSize>i[0]:\n",
    "                sum+=i[0]*i[1]\n",
    "                truckSize-=i[0]\n",
    "            else:\n",
    "                sum+=truckSize*i[1]\n",
    "                break\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(reverse=True, key=lambda x: x[1])\n",
    "        s, n = 0, 0\n",
    "        for k, v in boxTypes:\n",
    "            for _ in range(k):\n",
    "                if n >= truckSize:\n",
    "                    return s\n",
    "                s += v\n",
    "                n += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1],reverse=True)\n",
    "        res = 0\n",
    "        for x in boxTypes:\n",
    "            if x[0] < truckSize:\n",
    "                res += x[0] * x[1]\n",
    "            else:\n",
    "                res += truckSize * x[1]\n",
    "                return res\n",
    "            truckSize -= x[0]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes = sorted(boxTypes,key = (lambda x:x[1]),reverse= True)\n",
    "        res = 0\n",
    "        for i in range(0,len(boxTypes)):\n",
    "            if boxTypes[i][0]<=truckSize:\n",
    "                truckSize-= boxTypes[i][0]\n",
    "                res+=boxTypes[i][0]*boxTypes[i][1]\n",
    "            else:\n",
    "                res+=boxTypes[i][1]*truckSize\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while truckSize > 0 and i < len(boxTypes):\n",
    "            if boxTypes[i][0] < truckSize:\n",
    "                ans = ans + boxTypes[i][0] * boxTypes[i][1]\n",
    "                truckSize = truckSize - boxTypes[i][0]\n",
    "                i += 1\n",
    "            else:\n",
    "                ans = ans + truckSize * boxTypes[i][1]\n",
    "                truckSize = 0\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        ans = 0\n",
    "        for i,c in enumerate(boxTypes):\n",
    "            boxTypes[i] = c[::-1]\n",
    "        boxTypes.sort(reverse = True)\n",
    "        for a,b in boxTypes:\n",
    "            if b < truckSize:\n",
    "                ans += a * b\n",
    "                truckSize -= b\n",
    "            else:\n",
    "                ans += a * truckSize\n",
    "                return ans\n",
    "        return ans\n",
    "        print(boxTypes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        lis = sorted(boxTypes, key = lambda x:x[1], reverse = True)\n",
    "        #print(lis)\n",
    "        units = 0\n",
    "        for num, unit in lis:\n",
    "            units += min(truckSize, num) * unit\n",
    "            truckSize -= num\n",
    "            if truckSize <= 0:\n",
    "                return units\n",
    "        return units"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        n = len(boxTypes)\n",
    "\n",
    "\n",
    "        boxTypes = sorted(boxTypes, key=lambda x:-x[1])\n",
    "\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i<n and truckSize>0:\n",
    "            m, unit = boxTypes[i]\n",
    "            if truckSize>=m:\n",
    "                truckSize -= m\n",
    "                ans += m*unit\n",
    "            else:\n",
    "                ans += truckSize*unit\n",
    "                truckSize = 0 \n",
    "            i += 1\n",
    "        return ans \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes=sorted(boxTypes,key=lambda x:x[1],reverse=True)\n",
    "        sum_weight=0 #累加重量\n",
    "        list1=[]\n",
    "        for i in range(len(boxTypes)):\n",
    "            if(boxTypes[i][0]<=truckSize):\n",
    "                truckSize -=boxTypes[i][0]\n",
    "                weight = boxTypes[i][0] *boxTypes[i][1]\n",
    "                sum_weight += weight\n",
    "            elif(truckSize>0 and boxTypes[i][0]>truckSize):\n",
    "                weight = truckSize*boxTypes[i][1]\n",
    "                sum_weight +=weight\n",
    "                truckSize=0\n",
    "        return sum_weight\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1],reverse=True)\n",
    "        s = 0\n",
    "        c = 0\n",
    "        index = 0\n",
    "        while c < truckSize and index < len(boxTypes):\n",
    "            if truckSize - c > boxTypes[index][0]:\n",
    "                s += boxTypes[index][0] * boxTypes[index][1]\n",
    "                c += boxTypes[index][0]\n",
    "                index += 1\n",
    "            else:\n",
    "                s += (truckSize - c) * boxTypes[index][1]\n",
    "                c += boxTypes[index][0]\n",
    "                index += 1\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        n = len(boxTypes) \n",
    "        boxTypes.sort(key=lambda x : x[1] , reverse= True)\n",
    "        ans , pos = 0 , 0\n",
    "        for bn , size in boxTypes :\n",
    "            if bn >= truckSize :\n",
    "                ans += size * truckSize\n",
    "                break\n",
    "            ans += bn*size\n",
    "            truckSize -= bn\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x : x[1] , reverse = True)\n",
    "        print(boxTypes)\n",
    "        count = 0\n",
    "        for box in boxTypes:\n",
    "            if truckSize > 0:\n",
    "                if truckSize < box[0]:\n",
    "                    count += box[1] * truckSize\n",
    "                    break\n",
    "                else:\n",
    "                    truckSize -= box[0]\n",
    "                    count += box[1] * box[0]\n",
    "            else:\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x : x[1],reverse=True)\n",
    "        sum_ = 0\n",
    "        cnt = 0\n",
    "        for num,size in boxTypes:\n",
    "            if cnt + num <= truckSize:\n",
    "                cnt += num\n",
    "                sum_ += num*size\n",
    "            else:\n",
    "                sum_ += ((truckSize-cnt)*size)\n",
    "                break\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "    \n",
    "        boxTypes = sorted(boxTypes, key = lambda x: -x[-1])\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in boxTypes:\n",
    "            if cnt1 + i[0] <= truckSize:\n",
    "                cnt1 += i[0]\n",
    "                cnt2 += i[1] * i[0]             \n",
    "            else:\n",
    "                cnt2 += i[1] * (truckSize - cnt1)\n",
    "                return cnt2\n",
    "            \n",
    "        return cnt2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(reverse=True, key=lambda x: x[1])\n",
    "        s, n = 0, 0\n",
    "        for k, v in boxTypes:\n",
    "            s += k * v\n",
    "            n += k\n",
    "            if n == truckSize:\n",
    "                return s\n",
    "            elif n > truckSize:\n",
    "                while n > truckSize:\n",
    "                    n -= 1\n",
    "                    s -= v\n",
    "                return s\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x : x[1])\n",
    "\n",
    "        ans = 0\n",
    "        count = truckSize\n",
    "        for i in range(len(boxTypes) - 1, -1, -1):\n",
    "            tmp = min(count, boxTypes[i][0])\n",
    "            count -= tmp\n",
    "            ans += tmp * boxTypes[i][1]\n",
    "            if count == 0:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for box in boxTypes:\n",
    "            if truckSize > box[0]:\n",
    "                res += box[0] * box[1]\n",
    "                truckSize -= box[0]\n",
    "            else:\n",
    "                res += truckSize * box[1]\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x: x[1], reverse=True)\n",
    "        res = 0\n",
    "        for numberOfBoxes, numberOfUnitsPerBox in boxTypes:\n",
    "            if numberOfBoxes >= truckSize:\n",
    "                res += truckSize * numberOfUnitsPerBox\n",
    "                break\n",
    "            res += numberOfBoxes * numberOfUnitsPerBox\n",
    "            truckSize -= numberOfBoxes\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:x[1],reverse=True)\n",
    "        need=truckSize\n",
    "        res=0\n",
    "        while(boxTypes and  need>0):\n",
    "            cnt,value=boxTypes.pop(0)\n",
    "            if cnt>=need:\n",
    "                res+=need*value\n",
    "                need=0\n",
    "            else:\n",
    "                res+=cnt*value\n",
    "                need-=cnt\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():    \n",
    "    def maximumUnits(self, boxTypes, truckSize):\n",
    "        boxTypes = sorted(boxTypes, key = lambda x : x[1], reverse = True)\n",
    "        ret = 0\n",
    "        for box in boxTypes:\n",
    "            ret += min(truckSize, box[0]) * box[1]\n",
    "            truckSize -= min(truckSize, box[0])\n",
    "            if truckSize <= 0:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:x[1], reverse=True)\n",
    "        print(boxTypes)\n",
    "        res = 0\n",
    "        for cnt, cap in boxTypes:\n",
    "            if truckSize >= cnt:\n",
    "                truckSize -= cnt\n",
    "                res += cnt*cap\n",
    "            else:\n",
    "                res += cap*truckSize\n",
    "                truckSize = 0\n",
    "            if truckSize == 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        units = set(group[1] for group in boxTypes)  # 按单元数统计所有箱子共有几类（以防重复）\n",
    "        boxes = defaultdict(int)\n",
    "        for unit in units: boxes[unit] = 0\n",
    "        for group in boxTypes: boxes[group[1]] += group[0]\n",
    "        # 相同单元数的箱子已整合为一类\n",
    "        ans = 0\n",
    "        for unit in sorted(list(boxes), reverse = True):\n",
    "            if truckSize >= boxes[unit]:\n",
    "                ans += boxes[unit] * unit\n",
    "                truckSize -= boxes[unit]\n",
    "            else:\n",
    "                if truckSize == 0:\n",
    "                    return ans\n",
    "                else:\n",
    "                    return ans + truckSize * unit\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes= sorted(boxTypes,key=lambda x :-x[1])\n",
    "        #print(boxTypes)\n",
    "        k=truckSize\n",
    "        i=0\n",
    "        ans=0\n",
    "        while k>0 and i <len(boxTypes): \n",
    "            #print(boxTypes[i])\n",
    "            if boxTypes[i][0]>=k:\n",
    "                ans+=boxTypes[i][1]*k \n",
    "                k=0\n",
    "                #print(ans)\n",
    "            else:\n",
    "                ans+=boxTypes[i][0]*boxTypes[i][1]\n",
    "                k-=boxTypes[i][0]\n",
    "                i+=1\n",
    "                #print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:-x[1])\n",
    "        count=0\n",
    "        for i in boxTypes:\n",
    "            if i[0]<=truckSize:\n",
    "                truckSize-=i[0]\n",
    "                count+=i[0]*i[1]\n",
    "            else:\n",
    "                count+=i[1]*truckSize\n",
    "                break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key = lambda x: (x[1], x[0]), reverse=True)\n",
    "        ans = 0\n",
    "        for item in boxTypes:\n",
    "            if truckSize >= 0:\n",
    "                try_box = min(truckSize, item[0])\n",
    "                truckSize = truckSize - try_box\n",
    "                ans += try_box * item[1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        \n",
    "        boxunit = sorted(boxTypes,key=lambda x: x[1],reverse = True)\n",
    "        ans = 0\n",
    "        for k,v in boxunit:\n",
    "            temp = truckSize\n",
    "            truckSize = truckSize - k\n",
    "            if truckSize > 0:\n",
    "                ans += k*v\n",
    "            elif temp>0:\n",
    "                ans += temp*v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        score = 0\n",
    "        boxTypes = [[-item[1], item[0]] for item in boxTypes]\n",
    "        heapq.heapify(boxTypes)\n",
    "        while truckSize > 0 and len(boxTypes):\n",
    "            s, count = heapq.heappop(boxTypes)\n",
    "            s = -s\n",
    "            score += min(truckSize, count) * s\n",
    "            truckSize -= count\n",
    "        return score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:\n",
    "        boxTypes.sort(key=lambda x:x[1],reverse=True)\n",
    "        print(boxTypes)\n",
    "        ans = 0\n",
    "        for i,j in boxTypes:\n",
    "            ans += min(i,truckSize)*j\n",
    "            truckSize-=i\n",
    "            if truckSize<=0:\n",
    "                break\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
